package com.shuzijun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses{
    public static void main(String[] args) {
         
         Solution solution = new GenerateParentheses().new Solution();
        solution.generateParenthesis(3);
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private ArrayList<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        char[] path = new char[2 * n];
        backTrack(n,0,0,0,path);
        return result;
    }

        private void backTrack(int n, int leftUsed, int rightUsed, int k, char[] path) {
            if (k == 2*n){
                result.add(String.valueOf(path));
                return;
            }
            if (leftUsed < n){
                path[k] ='(';
                backTrack(n,leftUsed+1,rightUsed,k+1,path);
            }
            if (leftUsed > rightUsed){
                path[k] = ')';
                backTrack(n,leftUsed,rightUsed+1,k+1,path);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}